//
//#include <stdio.h>
//#include <assert.h>
//#include <stdbool.h>
//#include <stdlib.h>
//#include <string.h>

#include "queue.h"

typedef struct TreeNode
{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
}TreeNode;

TreeNode* BuyTreeNode(int x)
{
    TreeNode* newnode = (TreeNode*)malloc(sizeof(TreeNode));
    assert(newnode);

    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;

    return newnode;
}

TreeNode* BuyTree()
{
    TreeNode* n1 = BuyTreeNode(1);
    TreeNode* n2 = BuyTreeNode(2);
    TreeNode* n3 = BuyTreeNode(3);
    TreeNode* n4 = BuyTreeNode(4);
    TreeNode* n5 = BuyTreeNode(5);
    TreeNode* n6 = BuyTreeNode(6);
    
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;

    return n1;
}

void PreOrder(TreeNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(TreeNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

void PostOrder(TreeNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }

    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

void LevelOrder(TreeNode* root)
{
    Que q;
    QInit(&q);

    if (root)
    {
        QPush(&q, root);
    }
    
    while (!QEmpty(&q))
    {
        TreeNode* tmp = QFront(&q);
        QPop(&q);

        printf("%d ", tmp->data);

        if (tmp->left)
            QPush(&q, tmp->left);
        if (tmp->right)
            QPush(&q, tmp->right);
    }
    printf("\n");

    QDestroy(&q);
}

int TreeNodeSize(TreeNode* root)
{
    return root == NULL ? 0 : TreeNodeSize(root->left) + TreeNodeSize(root->right) + 1;
}

int TreeHeight(TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    
    int leftHeight = TreeHeight(root->left);
    int rightHeight = TreeHeight(root->right);

    return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

int TreeLeafSize(TreeNode* root)
{
    if (root == NULL) return 0;

    if (root->left == NULL && root->right == NULL) return 1;

    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

int TreeLKSize(TreeNode* root, int k)
{
    if (root == NULL) return 0;

    if (k == 1) return 1;

    return TreeLKSize(root->left, k - 1) + TreeLKSize(root->right, k - 1);
}

TreeNode* TreeNodeFind(TreeNode* root, int x)
{
    if (root == NULL) return NULL;

    if (root->data == x) return root;

    TreeNode* lret = TreeNodeFind(root->left, x);
    if (lret)
        return lret;

    TreeNode* rret = TreeNodeFind(root->right, x);
    if (rret)
        return rret;

    return NULL;
}

bool TreeComplate(TreeNode* root)
{
    Que q;
    QInit(&q);

    if (root)
        QPush(&q, root);
    
    while (!QEmpty(&q))
    {
        TreeNode* tmp = QFront(&q);
        QPop(&q);

        if (tmp == NULL) break;

        QPush(&q, tmp->left);
        QPush(&q, tmp->right);
    }

    while (!QEmpty(&q))
    {
        TreeNode* tmp = QFront(&q);
        QPop(&q);

        if (tmp)
        {
            QDestroy(&q);
            return false;
        }
    }

    QDestroy(&q);

    return true;
}

int main()
{
    TreeNode* root = BuyTree();

    PreOrder(root);
    printf("\n");
    InOrder(root);
    printf("\n");
    PostOrder(root);
    printf("\n");
    LevelOrder(root);

    printf("TreeNodeSize: %d\n", TreeNodeSize(root));
    printf("TreeHeight: %d\n", TreeHeight(root));
    printf("TreeLKSize: %d\n", TreeLKSize(root, 3));
    printf("TreeLeafSize: %d\n", TreeLeafSize(root));
    printf("TreeComplate: %d\n", TreeComplate(root));
    printf("TreeNodeFind 6 : %d -> %p\n", TreeNodeFind(root, 6)->data, TreeNodeFind(root, 6));

    return 0;
}
